Because there is always a possibility that a transmission error occurs in the field of information transmission, a means to detect and correct an error is needed. In an application field where a probability that a single error occurs during transmission (hereafter, referred to as a bit error rate) is relatively low, a coding scheme such as the extended Hamming coding scheme and high-dimensional parity coding scheme that has high coding efficiency and transmission efficiency is employed (see Non Patent Literatures (NPLS) 1 to 3).
FIG. 1 shows a general procedure for information transmission involving error correction. When a transmission system transmits information symbols X to a receiving system, the transmission system first generates a code word Y by adding, to the information symbols X, check symbols for error correction, using a coding device, and transmits the code word Y to the receiving system. Here, there is a possibility that a transmission error (E) occurs on a communication path due to disturbance, and part of a value of the code word Y changes. The code word received by the receiving system is denoted by Y′. FIG. 2 shows a relationship among the transmitted information symbols, check symbols, and code word. A code word having a length of N that is obtained by adding check symbols having a length of N−L to information symbols having a length of L is referred to as an (N, L) code. In addition, L/N is referred to as a code rate of the (N, L) code.
FIG. 3 shows a procedure for decoding and error correction. The receiving system decodes the received code word Y′, calculates information called a syndrome for error detection and correction, and checks whether or not the received code word Y′ includes a transmission error. When finding out that the code word Y′ includes a correctable error, the receiving system corrects the information symbols. Information symbols to be outputted by the decoding and error correcting circuit are denoted by Z. There are four scenarios below for an error included in the information symbols Z to be outputted, depending on the capability of an employed error detection and correcting scheme. The following describes a coding scheme which enables single error correction and double error detection.
(1) When an error does not occur on a transmission path, a decoding and error correcting circuit determines that a received code word Y′ does not include the error (Y′=Y).
(2) When an error (single error) that can be detected and corrected by a decoding and error correcting circuit occurs on a transmission path, the decoding and error correcting circuit can detect the single error included in a received code word Y′ and correct the single error to a correct value.
(3) When an error (double error) that can be detected but cannot be corrected by a decoding and error correcting circuit occurs on a transmission path, the decoding and error correcting circuit can detect the double error included in a received code word Y′ but cannot correct the double error to a correct value.
(4) When an error (at least 3-bit error) that cannot be detected by a decoding and error correcting circuit occurs on a transmission path, the decoding and error correcting circuit cannot detect the error included in a received code word Y′ and thus cannot correct the error to a correct value.
The following describes a coding and decoding method in the extended Hamming coding scheme that enable single error correction and double error detection are used, and an elementary operation used in the coding and decoding method. A single error correcting method in which simple Hamming codes are used is first described, and the extended Hamming coding scheme that enables single error correction and double error detection is then described.
(1-1) Coding and Decoding in which Hamming Codes are Used
A Hamming code is a (2n−1, 2n−1) code that constitutes a code word obtained by adding n-bit check symbols to information symbols having a length of L=2n−n−1 bits, and is a single error correcting code. For instance, when n=4, a (15, 11) code is calculated. Information symbols X and a code word Y are expressed below by Equation 1 and Equation 2, respectively.[Math. 1]X=[xL−1,xL−2, . . . ,x0],L=2n−n−1  (Equation 1)[Math. 2]Y=[yN−1,yN−2, . . . ,y0],N=2n−1  (Equation 2)
In the Hamming coding scheme, a generator matrix G is used for coding, and a check matrix H is used for decoding. The check matrix H is an n×(2n−1) matrix where each column includes all of n-dimensional column vectors except all zeros. FIG. 4 shows an exemplary check matrix H in the Humming coding scheme when n=4. The columns of the check matrix H may be arranged in any manner.
The generator matrix G corresponding to the check matrix H is a matrix that satisfies properties expressed by Equation 3. However, all additions (exclusive OR operation) are performed in modulo 2. GT and HT represent a transposed matrix of G and a transposed matrix of H, respectively. Hereafter, when a superior letter of a character representing a matrix is T, the character with the superior letter represents a transposed matrix of the matrix.[Math. 3]HGT=(GHT)T=0  (Equation 3)
When the check matrix H is expressed by Equation 4, a coding scheme is referred to as a systematic coding scheme.[Math. 4]H=[AIn]  (Equation 4)
Here, A represents a given n×(2n−n−1) matrix, and In represents an n×n identity matrix. In the systematic coding scheme, the generator matrix G corresponding to the check matrix H is easily determined by Equation 5.[Math. 5]G=┌IHLAT┐  (Equation 5)
Here, m=2n−n−1, and AT represents a transposed matrix of A. FIG. 5 shows the generator matrix G corresponding to the check matrix H shown by FIG. 4.
Coding is performed by multiplying the information symbols X by the generator matrix G. A code word obtained by coding the information symbols X is denoted by Y. For example, a code word corresponding to X=[10110111011] is Y=[101101110111100] as shown by FIG. 6.
Decoding and error correcting are performed in the following manner. It is assumed that a received code word is denoted by Y′, and the received code word includes at most a single error. Here, a syndrome S of the received code word Y′ is defined by Equation 6.[Math. 6]S=Y′HT  (Equation 6)
Whether or not the received code word includes an error is determined based on a value of the syndrome S in the following manner.
When all elements of S are 0, it is determined that the received code word has not included the transmission error.
When S includes an element that indicates a value other than 0, it is determined that the error has been at a location in a column of H that matches a vector obtained by transposing S.
For instance, in the above example, assuming that the transmission error occurs at the 8th bit from the left of the received code word and that the received code word is Y′=[101101100111100], a syndrome is S=[0111] as shown by FIG. 7. A transposed vector of S matches a value of the 8th column from the left of the check matrix H, and thus it is clear that the error is at the 8th bit from the left of the received code word. (Note that the location at which the bit error occurs is underlined.)
(1-2) Coding and Decoding in which Extended Hamming Codes are Used
Using Hamming codes enables single error correction. However, when a double error occurs, it is impossible to determine whether a single error or double error occurs, and thus correction cannot be performed accurately.
Extended Hamming codes obtained by extending Hamming codes are used as a method of performing single error correction and double error detection. A code word in the extended Hamming coding scheme is obtained by adding, to a code word resulting from coding using the generator matrix G, a parity bit of the whole code word (exclusive OR of all bits of the code word). Thus, a code word length in the extended Hamming coding scheme is 2n.
In the above example, a parity of the code word [101101110111100] obtained by applying the generator matrix G to the information symbols X=[10110111011] is 0, and thus 0 is added to the end of the code word to generate Y=[1011011101111000].
Decoding and error detection and correction in the extended Hamming coding scheme are performed using an extended check matrix H′ obtained by adding a column vector whose all elements are 0 after the last column of the check matrix H in the original Hamming coding scheme, and adding a vector whose all elements are 1 below the last row of the check matrix H. FIG. 8 shows the extended check matrix H′ corresponding to the check matrix H shown by FIG. 4.
When the error occurs at the 8th bit from the left of the code word in the example, the received code word is Y′=[101101100111100]. When a syndrome Y′H′T is calculated for the code word Y′ using the extended check matrix, [01111] is obtained as shown by FIG. 9.
A transposed vector of [01111], the multiplication result, matches a value of the 8th column from the left of the extended check matrix, and thus it is clear that the error occurs at the 8th bit from the left of the received code word. When the received code word includes a double error, the last element of Y′H′T is 0, because even numbers of 1 are included in the received code word. All the elements of the last row of the extended check matrix are 1, and thus a column vector obtained by transposing the check result does not match any column of the extended check matrix. In this case, it is determined that the double error has occurred. When an at least 3-bit error occurs, it is impossible to detect the at least 3-bit error. The above description can be summarized into <Case 1> to <Case 3> indicated below. Hereafter, a syndrome is represented by S=[sn−1, sn−2, . . . , s1, 0, r]. In addition, or (element 1, element 2, . . . , element n) is a logic function for calculating a logical sum of all elements.
<Case 1> When all elements of S are 0 (r=0 and or (sn−1, sn−2, . . . , s1, s0)=0), it is determined that an error has not occurred.
<Case 2> When the element r=1 in S, it is determined that a single error has occurred. A location where the error occurs is an element corresponding to a column having a pattern that matches S.
<Case 3> In a case other than <Case 1> and <Case 2> (r=0 and or (sn−1, sn−2, . . . , s1, s0)=1), it is determined that a double error has occurred.
Next, conventional methods of implementing a device for coding and a device for decoding and error correcting can be classified into the following two types: (A) Implementation using software on a general-purpose processor (hereafter, referred to as a conventional method (A)); and (B) Implementation using dedicated hardware (ASIC: Application Specific Integrated Circuit) (hereafter, referred to as a conventional method (B)).
FIG. 10 is a diagram showing implementation of conventional error-correcting code processing, using software on a general-purpose processor. In FIG. 10, an instruction memory 111 and a data memory 112 are outside of a general-purpose processor 110. The instruction memory 111 holds instructions for coding operations and decoding operations in the error-correcting code processing. The general-purpose processor 110 performs a coding operation and a decoding operation in the error-correcting code processing according to an instruction read from the instruction memory 111. Moreover, the general-purpose processor 110 reads data held in the data memory 112 via a data bus 113, according to an instruction read from the instruction memory 111. Furthermore, the general-purpose processor 110 stores the results of the operations performed, into the data memory 112 via the data bus 113.
FIG. 11 is a diagram showing implementation of the conventional error-correcting code processing, using a general-purpose processor and a dedicated peripheral circuit (ASIC). In FIG. 11, an instruction memory 121, a data memory 122, a coding circuit 123, and a decoding circuit 124 are outside of a general-purpose processor 120. The instruction memory 121 holds instructions for coding operations and decoding operations in the error-correcting code processing. The general-purpose processor 120 reads data and a command specifying a process to be performed that are held in the data memory 122 via a data bus 125, according to an instruction read from the instruction memory 121, and transmits the command and data to the coding circuit 123 and the decoding circuit 124 via the data bus 125. Moreover, the general-purpose processor 120 reads, from the coding circuit 123 and the decoding circuit 124, status information indicating whether coding and decoding are possible or the like and the results of operations after the coding and decoding, and stores the status information and the results of the operations into the data memory 122 via the data bus 125. The coding circuit 123 performs a coding operation in the error-correcting code processing according to an instruction read from the instruction memory 121. The decoding circuit 124 performs a decoding operation in the error-correcting code processing according to an instruction read from the instruction memory 121. Here, the coding circuit 123 and the decoding circuit 124 include the ASIC. In addition, the coding circuit 123 generates check symbols, and the decoding circuit 124 generates a syndrome and corrects an error.
The following trade-offs exist between the convention methods (A) and (B).
In comparison with the conventional method (B), the conventional method (A) has the following advantages: (a) a smaller hardware amount required for implementation (it is sufficient to provide only a memory for storing programs.); and (b) more flexibility in responding to a change of specifications (it is possible to easily respond to a change of a coding scheme or a code length.).
However, in comparison with the convention method (B), the conventional method (A) has the following disadvantages: (c) a longer execution time (a larger number of execution cycles); and (d) a larger power consumption.